//给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下： 
//
// 
// 二叉树的根是数组 nums 中的最大元素。 
// 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。 
// 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。 
// 
//
// 返回有给定数组 nums 构建的 最大二叉树 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,2,1,6,0,5]
//输出：[6,3,5,null,2,0,null,null,1]
//解释：递归调用如下所示：
//- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
//    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
//        - 空数组，无子节点。
//        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
//            - 空数组，无子节点。
//            - 只有一个元素，所以子节点是一个值为 1 的节点。
//    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
//        - 只有一个元素，所以子节点是一个值为 0 的节点。
//        - 空数组，无子节点。
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,1]
//输出：[3,null,2,null,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 1000 
// nums 中的所有整数 互不相同 
// 
// 👍 338 👎 0


package leetcode.editor.cn;

//最大二叉树

import Entity.TreeNode;
import 分类.二叉树;

import java.util.Arrays;

public class P654_最大二叉树 implements 二叉树 {
    public static void main(String[] args) {
        Solution solution = new P654_最大二叉树().new Solution();
        int[] nums = {3,2,1,6,0,5};
        TreeNode treeNode = solution.constructMaximumBinaryTree(nums);
        System.out.println(treeNode);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 只用关心一个节点的操作即可
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            if (nums.length == 0) {
                return null;
            }
            if (nums.length == 1) {
                return new TreeNode(nums[0]);
            }
            // 找到根节点 即数组的最大值
            int max = Integer.MIN_VALUE;
            int pos = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > max) {
                    pos = i;
                    max = nums[i];
                }
            }
            TreeNode root = new TreeNode(max);
            // 对pos进行分割
            int[] left = Arrays.copyOfRange(nums, 0, pos);
            TreeNode leftNode = constructMaximumBinaryTree(left);
            int[] right = Arrays.copyOfRange(nums, pos + 1, nums.length);
            TreeNode rightNode = constructMaximumBinaryTree(right);
            root.left = leftNode;
            root.right = rightNode;
            return root;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}